package Partition;

import java.util.Random;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-02-07
 * Time:19:41
 * Text：数组中的第K个最大元素
 */
public class Text3 {
    public static void swap(int[] nums,int left,int right){
        int tem=nums[right];
        nums[right]=nums[left];
        nums[left]=tem;
    }
    public static int findKthLargest(int[] nums, int k) {
        int mid=quick(nums,0,nums.length-1,nums.length-k);
        return mid;
    }
    public static int quick(int[] nums,int l,int r,int k){
        int num=0;
        if(l>=r)
            return nums[l];
        int key=nums[new Random().nextInt(r-l+1)+l];
        int left = l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]>key) swap(nums,--right,i);
            else i++;
        }
        if(k>=right){
            num= quick(nums,right,r,k);
        }else if(k<=left){
            num=quick(nums,l,left,k);
        }else if(left<k && k<right){
            num=nums[k];
        }
        return num;
    }

    public static void main(String[] args) {
        int[] arr={1,4,3,5,8,7,2,3,4};
        System.out.println(findKthLargest(arr,5));
    }
}
